1. Field of the Invention
The present application generally relates to methods and apparatuses for construction of codes for data-compression and, more particularly, to a method and apparatus for constructing efficient Slepian-Wolf codes for mismatched coding.
2. Background Description
Slepian-Wolf codes refer to codes used for compressing source data at an encoder, where the decoder has access to side information not available to the encoder. There are many applications of these codes. Examples of such applications include, but are not limited to, low complexity encoding of media, distributed source coding for sensor networks, scalable video coding, etc.
FIG. 1 shows a generic Slepian-Wolf coding system. The signal Xn=X1X2 . . . Xn, termed the Slepian-Wolf source 100, is compressed by the encoder 101 using a Slepian-Wolf code, the output of which is a set of symbols termed syndromes 102. These syndromes represent the compressed source signal. The decoder 103 receives a signal Yn=Y1Y2 . . . Yn, termed the Slepian-Wolf side information 104, which is used to decode the signal Xn from the syndromes. Without loss of generality, it can be assumed that Xi and Yi take values in discrete sets {0, 1, . . . , M−1} and {0, 1 . . . , N−1}, respectively, for all i=1, 2, . . . , n. The efficiency of compression (measured by the bit rate of the syndromes required to decode X successfully) depends, among other factors, on the joint distribution of Xi and Yi (denoted by PXY), the goodness of the Slepian-Wolf code employed, and the decoding method. The better the Slepian-Wolf code, the lower is the number of syndrome bit required for successful decoding for a given joint distribution and a decoding method.
Previous methods for designing Slepian-Wolf code are reported by S. S. Pradhan and K. Ramchandran, “Distributed source coding using syndromes (DISCUS): design and construction”, IEEE Transactions on Information Theory, pp. 626-643, March 2003, J. Garcia-Frais and Y. Zhao, “Compression of correlated binary sources using turbo codes”, IEEE Communication Letters, 5:417-419, October 2001, V. Stankovic, A. Liveris, Z. Xiong, and C. Georghiades, “On code design for the general Slepian-Wolf problem and for lossless multiterminal communications networks”, IEEE Transactions on Information Theory, pp. 1495-1507, April 2006, J. Bajcsy and P. Mitran, “Coding for the Slepian-Wolf problem with turbo codes”, IEEE Globecom. pp. 1400-1404, November 2001, A. Aaron and B. Girod, “Compression with side information using turbo codes”, Proceedings of the IEEE Data Compression Conference (DCC), pp. 252-261, April 2002, A. D. Liveris et al., “Compression of binary sources with side information at the decoder using LDPC codes”, IEEE Communication Letters, vol. 6, pp. 440-442, 2002, J. Chen, D. He and A. Jagmohan, “Slepain-Wolf code design via source-channel correspondence”, Proceedings of IEEE International Symposium on Information Theory, July 2006. These methods are developed under the assumption that the joint distribution PXY is perfectly known and the decoder uses a decoding metric that is matched to PXY.
FIG. 2 shows an exemplary conventional method for constructing Slepian-Wolf codes. The input 200 to the design method is the probability distribution PXY. The joint distribution 200 is first converted to a cyclic-symmetric channel distribution 201, i.e., QV|U, with input alphabet {0, 1, . . . , M−1} and output alphabet {0, 1, . . . , M−1}×{0, 1, . . . , N−1}. The channel QV|U is related to PXY through the equation V=(U+MX,Y), where U is independent of (X,Y) whose distribution is PXY, and +M denotes modulo-M addition. The cyclic-symmetric channel QV|U is then used to compute the initial message value 202, i.e., m0(ν), through the equation:
                    m        0            ⁡              (        v        )              =          [                        log          ⁢                                                    Q                                  V                  |                  U                                            ⁡                              (                                  v                  |                  1                                )                                                                    Q                                  V                  |                  U                                            ⁡                              (                                  v                  |                  0                                )                                                    ,                  log          ⁢                                                    Q                                  V                  |                  U                                            ⁡                              (                                  v                  |                  2                                )                                                                    Q                                  V                  |                  U                                            ⁡                              (                                  v                  |                  0                                )                                                    ,        …        ⁢                                  ,                  log          ⁢                                                    Q                                  V                  |                  U                                            ⁡                              (                                  v                  |                                      M                    -                    1                                                  )                                                                    Q                                  V                  |                  U                                            ⁡                              (                                  v                  |                  0                                )                                                        ]        ,      v    ∈                  {                  01          ,          …          ⁢                                          ,                      M            -            1                          }            ×              {                  0          ,          1          ,          …          ⁢                                          ,                      N            -                              The initial message value m0(ν) and the probability distribution PXY are used to determine the probability distribution of m0 (V), i.e., Pm0 203 by setting the probability distribution of V equal to PXY. Given Pm0, the density evolution means 204, which consists of the density evolution algorithm and the standard degree distribution optimization methods, outputs an optimized degree distribution 205. The construction of Slepian-Wolf codes given the degree distribution is straightforward.
However, for real applications, it is impossible to obtain a completely accurate estimation of the joint probability distribution PXY. Let {circumflex over (P)}XY denote the estimated probability distribution that is used by the decoder to recover the source signal Xn given the syndromes and the side information Yn. For the case in which {circumflex over (P)}XY is different from PXY, the decoder is mismatched to the true probability distribution (and therefore, the decoding is referred to as mismatched decoding). For practical Slepian-Wolf coding systems, it is essential that the imperfect knowledge of PXY is taken into account when designing Slepian-Wolf codes. It is also important to choose the optimal decoding metric in the mismatched decoding case, where the decoding metric is the joint probability distribution used for decoding. However, there are no previously known computationally feasible methods for constructing good Slepian-Wolf codes with mismatched decoding and choosing the optimum decoding metric.
Therefore, a need exists for an improved method for Slepian-Wolf code design wherein mismatched decoding resulting from the imperfect knowledge of joint probability distribution is taken into account. There also exists a need for an improved method for choosing the optimal decoding metric in the mismatched decoding case.